package _interview150;

/**
 * 36. 有效的数独
 */
public class No36 {
    /**
     * 1. 模拟
     */
    public boolean isValidSudoku1(char[][] board) {
        // 按行
        for (char[] row : board) {
            if (!isValid(row)) return false;
        }
        // 按列
        for (int j = 0; j < 9; j++) {
            char[] temp = new char[9];
            for (int i = 0; i < 9; i++) {
                temp[i] = board[i][j];
            }
            if (!isValid(temp)) return false;
        }
        // 按方格
        for (int j = 0; j < 9; j += 3) {
            for (int i = 0; i < 9; i += 3) {
                char[] temp = new char[9];
                System.arraycopy(board[i], j, temp, 0, 3);
                System.arraycopy(board[i + 1], j, temp, 3, 3);
                System.arraycopy(board[i + 2], j, temp, 6, 3);
                if (!isValid(temp)) return false;
            }
        }
        return true;
    }

    private boolean isValid(char[] chars) {
        char[] temp = new char[9];
        for (char c : chars) {
            if (Character.isDigit(c) && ++temp[c - '1'] > 1) return false;
        }
        return true;
    }

    /**
     * 2. 一次遍历
     */
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] columns = new boolean[9][9];
        boolean[][] areas = new boolean[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (!Character.isDigit(c)) continue;
                int num = c - '1';
                boolean[] area = areas[(i / 3) * 3 + j / 3];
                if (rows[i][num] || columns[j][num] || area[num]) return false;
                rows[i][num] = true;
                columns[j][num] = true;
                area[num] = true;
            }
        }
        return true;
    }
}
